package pers.qianyu.month_202101.date_20210127;

import pers.qianyu.util.model.*;

import java.util.*;

/**
 * 49. 二叉搜索树与双向链表
 * https://www.acwing.com/problem/content/87/
 *
 * @author mizzle rain
 * @date 2021年1月27日17:42:20
 */
public class Convert {
    public TreeNode convert(TreeNode root) {
        if (root == null) return null;
        TreeNode pre = null, p = root;
        Deque<TreeNode> st = new LinkedList<>();
        while (p != null || !st.isEmpty()) {
            while (p != null) {
                st.addLast(p);
                p = p.left;
            }
            TreeNode node = st.pollLast();
            if (node.right != null) p = node.right;
            node.left = pre;
            if (pre != null) pre.right = node;
            pre = node;
        }
        while (pre.left != null) pre = pre.left;
        return pre;
    }
}